package couk.psyked.box2d.utils.shape
{

    public class Triangulate
    {

        private static var EPSILON:Number = 0.0000000001;

        public function Triangulate()
        {
        	//constructor 
        }

        public function process( contour:Array ):Array
        {
            var result:Array = new Array();
            var n:int = contour.length;

            if ( n < 3 )
            {
                return null;
            }

            var verts:Array = new Array();

            /* we want a counter-clockwise polygon in verts */
            var v:int;
            if ( 0.0 < area( contour ))
            {
                //for ( v in 0...n )
                for ( v = 0; v < n; v++ )
                {
                    verts[ v ] = v
                }
            }
            else
            {
                //for ( v in 0...n )
                for ( v = 0; v < n; v++ )
                {
                    verts[ v ] = ( n - 1 ) - v;
                }
            }
            var nv:int = n;
            /*  remove nv-2 vertsertices, creating 1 triangle every time */
            var count:int = 2 * nv; /* error detection */

            var m:int;
            m = 0;
            v = nv - 1;
            while ( nv > 2 )
            {
                /* if we loop, it is probably a non-simple polygon */
                if ( 0 >= ( count-- ))
                {
                    //** Triangulate: ERROR - probable bad polygon!
                    //trace("bad poly");
                    return null;
                }

                /* three consecutive vertices in current polygon, <u,v,w> */
                var u:int = v;
                if ( nv <= u )
                {
                    u = 0; /* previous */
                }
                v = u + 1;
                if ( nv <= v )
                {
                    v = 0; /* new v	*/
                }
                var w:int = v + 1;
                if ( nv <= w )
                {
                    w = 0; /* next	 */
                }
                if ( snip( contour, u, v, w, nv, verts ))
                {

                    var a:int, b:int, c:int, s:int, t:int;

                    /* true names of the vertices */
                    a = verts[ u ];
                    b = verts[ v ];
                    c = verts[ w ];

                    /* output Triangle */
                    result.push( contour[ a ]);
                    result.push( contour[ b ]);
                    result.push( contour[ c ]);

                    m++;

                    /* remove v from remaining polygon */
                    s = v;
                    t = v + 1;
                    while ( t < nv )
                    {
                        verts[ s ] = verts[ t ];
                        s++;
                        t++;
                    }
                    nv--;

                    /* resest error detection counter */
                    count = 2 * nv;
                }
            }
            return result;
        }

        // calculate area of the contour polygon
        public function area( contour:Array ):Number
        {
            var n:int = contour.length;
            var a:Number = 0.0;
            var p:int = n - 1;
            var q:int = 0;
            while ( q < n )
            {
                a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y;
                p = q++;
            }
            return a * 0.5;
        }

        // see if p is inside triangle abc
        public function insideTriangle( ax:Number, ay:Number, bx:Number, by:Number, cx:Number, cy:Number, px:Number, py:Number ):Boolean
        {
            var aX:Number, aY:Number, bX:Number, bY:Number;
            var cX:Number, cY:Number, apx:Number, apy:Number;
            var bpx:Number, bpy:Number, cpx:Number, cpy:Number;
            var cCROSSap:Number, bCROSScp:Number, aCROSSbp:Number;
            aX = cx - bx;
            aY = cy - by;
            bX = ax - cx;
            bY = ay - cy;
            cX = bx - ax;
            cY = by - ay;
            apx = px - ax;
            apy = py - ay;
            bpx = px - bx;
            bpy = py - by;
            cpx = px - cx;
            cpy = py - cy;
            aCROSSbp = aX * bpy - aY * bpx;
            cCROSSap = cX * apy - cY * apx;
            bCROSScp = bX * cpy - bY * cpx;
            return (( aCROSSbp >= 0.0 ) && ( bCROSScp >= 0.0 ) && ( cCROSSap >= 0.0 ));
        }

        private function snip( contour:Array, u:int, v:int, w:int, n:int, verts:Array ):Boolean
        {
            var p:int;
            var ax:Number, ay:Number, bx:Number, by:Number;
            var cx:Number, cy:Number, px:Number, py:Number;
            ax = contour[ verts[ u ]].x;
            ay = contour[ verts[ u ]].y;
            bx = contour[ verts[ v ]].x;
            by = contour[ verts[ v ]].y;
            cx = contour[ verts[ w ]].x;
            cy = contour[ verts[ w ]].y;
            if ( EPSILON > ((( bx - ax ) * ( cy - ay )) - (( by - ay ) * ( cx - ax ))))
            {
                return false;
            }
            //for ( p in 0...n )
            for ( p = 0; p < n; p++ )
            {
                if (( p == u ) || ( p == v ) || ( p == w ))
                {
                    continue;
                }
                px = contour[ verts[ p ]].x;
                py = contour[ verts[ p ]].y;
                if ( insideTriangle( ax, ay, bx, by, cx, cy, px, py ))
                {
                    return false;
                }
            }
            return true;
        }
    }
}